import java.util.Arrays;

public class quikSort {
    public static void main(String[] args) {
     int [] array ={1,8,3,2,6,4,5,7,9};
       qsMj(array,null,null);
        System.out.println(Arrays.toString(array));
    }
    public static void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[]array , int start, int end){
        if (start >= end){
            return;
        }
        int pivot = array[start];
        int left = start;
        int right = end;
        while(left <= right){
            while(left<=right && array[left] < pivot){
                left++;
            }
            while(left <= right && array[right] > pivot){
                right--;
            }
            if (left <= right){
                int temp =array[left];
                array[left] = array[right];
                array[right] =temp;
                left++;
                right--;
            }
        }
    }

    public  static  void qsMj(int[]array,Integer pIndex ,Integer right){
        //基点坐标
        if (pIndex == null){
            pIndex = 0;
        }
        //基点
        int pivot = array[pIndex];
        //左指针
        int left = pIndex+1;
        //最终基点位置
        int position = 0;
        //右指针
        if (right == null){
            right = array.length-1;
        }
        while(left < right){
            if (array[left] >= pivot){
                left++;
            }
            if (array[left]<pivot){
                swap(array,array[left],pivot);
                left ++;
                right --;
            }
        }
        if (left == right){
            position =left=right;
        }
        pIndex++;
        qsMj(array,pIndex,position);
        if (position != array.length-1){
            qsMj(array,position, array.length-1);
        }


    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
